package com.yeban.issue;

import java.util.ArrayList;
import java.util.List;

/**
 * @Desc TODO
 * @Author yeban
 * @Date 2025/10/7
 */
// 自测n皇后
public class Demo {

    List<List<String>> res = new ArrayList<>();

    // 递归函数
    public void backTrack(int n, int row, char[][] chessBoard) {

        if(row == n) {
            res.add(push_back(chessBoard));
        }

        for (int i = 0; i < n; i++) {   // 遍历当前行中的每一列
            if(isValid(row,i,chessBoard,n)) {
                chessBoard[row][i] = 'Q';   // 放置皇后
                backTrack(n,row+1,chessBoard);
                chessBoard[row][i] = '.';   // 回溯皇后
            }
        }
    }

    // 存档结果
    public List push_back(char[][] chessBoard) {
        List<String> list = new ArrayList<>();

        for(char[] c : chessBoard) {
            list.add(String.valueOf(c));
        }

        return list;
    }

    // 判断是否可以放置皇后
    public Boolean isValid(int row, int col, char[][] chessBoard, int n) {

        // 判断列
        for (int i = 0; i < row; i++) {
            if(chessBoard[i][col] == 'Q') {
                return false;
            }
        }

        // 判断负对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0 ; i--, j--) {
            if(chessBoard[i][j] == 'Q') {
                return false;
            }
        }

        // 判断正对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < n ; i--, j++) {
            if(chessBoard[i][j] == 'Q') {
                return false;
            }
        }

        return true;
    }

    public static void main(String[] args) {

    }
}
